package com.example.question.dp.dp1;

public class Code09_300 {
    public static void main(String[] args) {
        Code09_300 code = new Code09_300();
        int i = code.lengthOfLIS1(new int[]{0, 1, 0, 3, 2, 3});
        System.out.println(i);
    }

    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        // 每个的值至少为1
        // Arrays.fill(dp, 1);
        dp[0] = 1;
        int maxLen = 1;
        for (int i = 1; i < nums.length; i++) {
            boolean flag = false;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                    maxLen = Math.max(maxLen, dp[i]);
                    flag = true;
                }
            }
            if (!flag) {
                dp[i] = 1;
            }
        }
        return maxLen;
    }

    // [10,9,2,5,3,7,101,18]
    //  1  1 1 2 2 3  4  4
    public int lengthOfLIS1(int[] nums) {
        // dp[i] = dp[i-1]+1 (nums[i]> nums[i-1])
        //
        Helper[] helpers = new Helper[nums.length];
        helpers[0] = new Helper(1, nums[0]);
        int max = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (helpers[j].num < nums[i] && helpers[j].index == max) {
                    helpers[i] = new Helper(helpers[j].index + 1, nums[i]);
                    break;
                }
                if (j == 0) {
                    helpers[i] = new Helper(1, nums[i]);
                }
            }
            max = Math.max(max, helpers[i].index);
        }

        return max;
    }

    static class Helper {
        private int index;
        private int num;

        public Helper(int index, int num) {
            this.index = index;
            this.num = num;
        }
    }

}
